// https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> next = nextArr(needle);
        int n = haystack.size();
        int m = needle.size();
        int i = 0, j = 0;

        while (i < n) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    i++;
                }
            }

            if (j == m) return i - m;
        }
        return -1;
    }

    vector<int> nextArr(string s) {
        int n = s.size();
        vector<int> next(n, 0);
        int prefix = 0, i = 1;

        while (i < n) {
            if (s[i] == s[prefix]) {
                prefix++;
                next[i] = prefix;
                i++;
            } else {
                if (prefix > 0) {
                    prefix = next[prefix - 1];
                } else {
                    next[i] = 0;
                    i++;
                }
            }
        }
        return next;
    }
};